package org.xqh.study.leetcode.algorithm;

import com.alibaba.fastjson.JSON;

/**
 * @ClassName RotateArray
 * @Description 旋转数组
 * @Author xuqianghui
 * @Date 2021/1/8 16:13
 * @Version 1.0
 */
public class RotateArray {

    public static void main(String[] args) {
        int[] nums = {2, 5, 6, 11, 18};
        rotate2(nums, 5);
        System.out.println(JSON.toJSONString(nums));
    }

    public static void rotate(int[] nums, int k) {
        int len = nums.length;
        k = k % len;
        if(k != 0){
            int[] retNums = new int[len];
            for(int i = 0; i < len; i++){
//                retNums[i] = nums[(len-k+i)%len];
                retNums[(i+k) % len] = nums[i];
            }
            System.arraycopy(retNums, 0, nums, 0, len);
            System.out.println(JSON.toJSONString(nums));
        }
    }

    public static void rotate2(int[] nums, int k) {
        int len = nums.length;
        k = k % len;
        if(k != 0){
            flipArray(nums, 0, len);//整个数组 倒排
            flipArray(nums, 0, k);
            flipArray(nums, k, len - k);
        }
    }

    /**
     * 翻转数组
     * @param nums
     * @param start
     * @param len
     */
    public static void flipArray(int[] nums, int start, int len){
        int count = (len + 1) / 2;
        for(int i = 0; i < count; i ++){
            int tmp = nums[i + start];
            nums[i + start] = nums[len + start - i - 1];
            nums[len + start - i - 1] = tmp;
        }
    }

    /**
     * 环形旋转
     * @param nums
     * @param k
     */
    public static void rotate3(int[] nums, int k) {
        int len = nums.length;
        k = k % len;
        if(k != 0){
            for(int i = 0; i < len; i++){
                nums[(i+k)%len] = nums[i];
            }
        }
    }
}